package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/26/20 6:52 PM
 *
 *  https://leetcode-cn.com/problems/maximal-rectangle/
 */
public class _85_最大矩形_01 {

    public int maximalRectangle(char[][] matrix) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {

            return 0;
        }

        int max = 0;

        int[] eachLineOneCount = new int[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {

            for (int j = 0; j < matrix[i].length; j++) {

                if (matrix[i][j] == '0') {

                    eachLineOneCount[j] = 0;
                }else {

                    eachLineOneCount[j] += 1;
                }
            }

            max = Math.max(max,largestRectangleArea(eachLineOneCount));
        }

        return max;
    }

    private int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }

        if (heights.length == 1) {

            return heights[0];
        }

        int len = heights.length;
        int[] leftToRight = new int[len];
        int[] rightToLeft = new int[len];

        leftToRight[0] = -1;

        for (int i = 1; i < len; i++) {

            leftToRight[i] = -1;
            int curVal = heights[i];
            int preIndex = i - 1;

            while (preIndex >= 0) {

                if (heights[preIndex] <= curVal) {

                    leftToRight[i] = (heights[preIndex]== curVal?leftToRight[preIndex]:preIndex);
                    break;
                }else {

                    preIndex = leftToRight[preIndex];
                }
            }
        }

        rightToLeft[len - 1] = len;
        for (int i = len - 2; i >= 0; i--) {

            rightToLeft[i] = len;
            int curVal = heights[i];
            int nextIndex = i + 1;

            while (nextIndex < len) {

                if (heights[nextIndex] <= curVal) {

                    rightToLeft[i] = (heights[nextIndex]==curVal?rightToLeft[nextIndex]:nextIndex);
                    break;
                }else {

                    nextIndex = rightToLeft[nextIndex];
                }
            }
        }

        int max = 0;

        for (int i = 0; i < len; i++) {

            max = Math.max(max,heights[i] * (rightToLeft[i] - leftToRight[i] - 1));
        }

        return max;
    }
}
